//  All code copyright (c) 2003 Barry Lapthorn
//  Website:  http://www.lapthorn.net
//
//  Disclaimer:  
//  All code is provided on an "AS IS" basis, without warranty. The author 
//  makes no representation, or warranty, either express or implied, with 
//  respect to the code, its quality, accuracy, or fitness for a specific 
//  purpose. Therefore, the author shall not have any liability to you or any 
//  other person or entity with respect to any liability, loss, or damage 
//  caused or alleged to have been caused directly or indirectly by the code
//  provided.  This includes, but is not limited to, interruption of service, 
//  loss of data, loss of profits, or consequential damages from the use of 
//  this code.
//
//
//  $Author: barry $
//  $Revision: 1.1 $
//
//  $Id: GA.cs,v 1.1 2003/08/19 20:59:05 barry Exp $
//
//  Modified by Lionel Monnier 30th aug 2004

#region Using directives

using System;
using CombinatorialObjects;

#endregion

namespace Salesman.Genetic
{

    class PermutationGenomeFactory : IGenomeFactory
    {
        private readonly int size;

        public PermutationGenomeFactory(int size)
        {
            this.size = size;
        }

        public Genome CreateGenome()
        {
            return new PermutationGenome(size);
        }
    }

    /// <summary>
    /// Summary description for Genome.
    /// </summary>
    public sealed class PermutationGenome : Genome
    {
        private static readonly Random random = new Random();
        private Permutation genes;
        private readonly int length;
        private readonly IGenomeFactory genomeFactory;

        public PermutationGenome(int length) : this(length, true)
        {
        }
        public PermutationGenome(int length, bool createGenes)
        {
            genomeFactory = new PermutationGenomeFactory(this.length);
            this.length = length;
            genes = new Permutation(length);
            if (createGenes)
                CreateGenes();
        }

        public PermutationGenome(ref Permutation genes)
        {
            genomeFactory = new PermutationGenomeFactory(length);
            length = genes.Order;
            this.genes = genes.Clone();
        }


        public int Length
        {
            get { return length; }
        }

        public Permutation Genes
        {
            get { return genes; }
        }
        public override IGenomeFactory GenomeFactory
        {
            get { return genomeFactory; }
        }

        public override Genome Clone()
        {
            var g = new PermutationGenome(length, false)
                    {
                        genes = genes.Clone()
                    };
            return g;
        }

        protected override void CreateGenes()
        {
            genes.Randomize(random);
        }


        public override void Mutate(double mutationRate)
        {
            for (int pos = 0; pos < length; pos++)
            {
                if (random.NextDouble() < mutationRate)
                    Genes.Swap(pos, random.Next(length));
            }
        }

        static Random _random = new Random();

        public override void CrossOverWith(Genome other, out Genome child1, out Genome child2)
        {
            var otherP = other as PermutationGenome;
            if (otherP == null)
                throw new ArgumentException();
            var permutations = CrossOverOX(genes, otherP.genes);
            child1 = new PermutationGenome(ref permutations[0]);
            child2 = new PermutationGenome(ref permutations[1]);
        }
        static Permutation[] CrossOverOX(params Permutation[] we)
        {
            int perversion = we.Length; // number of parents (size of an orgy)
            if (perversion < 2)
                throw new ArgumentException();
            int order = we[0].Order;
            var B = new Permutation[perversion];
            // Z. Michalewicz, "Algorytmy genetyczne (...)" wyd 3, p. 52

            // OX crossover
            // 1. Choose a subsequence from a boy
            int start = _random.Next(order - 1);
            int end = _random.Next(start+1, order);
            // for each parent
            for (int j = 0; j < perversion; j++)
            {
                var check = new bool[order];
                Permutation p1 = we[j];
                Permutation p2 = we[perversion - j - 1];
                Permutation b = (B[perversion - j - 1] = new Permutation(order));
                // 2. Put the subsequence into a child
                for (int i = start; i <= end; i++)
                {
                    b.DataUnsafe[i] = p1.DataUnsafe[i];
                    check[b.DataUnsafe[i]] = true;
                }
                // 3. Fill the rest
                int pi = end;
                for (int i = end + 1; i < order; i++)
                {
                    do
                    {
                        pi++;
                        if (pi == order) pi = 0;
                    } while (check[p2.DataUnsafe[pi]]);
                    b.DataUnsafe[i] = p2.DataUnsafe[pi];
                    check[b.DataUnsafe[i]] = true;
                }
                for (int i = 0; i < start; i++)
                {
                    do
                    {
                        pi++;
                        if (pi == order) pi = 0;
                    } while (check[p2.DataUnsafe[pi]]);
                    b.DataUnsafe[i] = p2.DataUnsafe[pi];
                }
                b.CheckPermutation();
            }
            return B;
        }

    }
}